//树剖LCA
int dfs1(int u,int f){
	size[u] = 1, vis[u] = 1;
	for(int i = head[u]; i; i = e[i].next){
		int v = e[i].to;
		if(v = f) continue;
		depth[v] = depth[u] + 1;
		fa[v] = u;
		dfs(v, u);
		size[u] += size[v];
		if(size[v] > size[son[u]])
			son[u] = v;
	}
}
int dfs2(int u,int t){
	top[u] = t;
	if(son[u]) dfs2(son[u], t);
	for(int i = head[x]; i; i = e[i].next){
		int v = e[i].to;
		if(v == fa[v] || v ==son[u]) continue;
		dfs2(v, v);
	}
}
int LCA(int u,int v){
    while(top[u] != top[v]){
        if(depth[top[u]] > depth[top[v]])
			u = fa[top[u]];
        else v = fa[top[v]];
    }
    return dep[u] < dep[v] ? u : v;
}


//倍增LCA
void dfs(int u,int fa){
    dep[u] = dep[fa]+1;
    for(int i = 0; f[u][i]; i++)
        f[u][i+1] = f[f[u][i]][i];
    for(int i = head[u]; i; i = edge[i].next){
        int v=edge[i].to;
        if(v == fa)continue;
        f[v][0] = u;
        dfs(v, u);
    }
}
int lca(int x,int y){
	if(depth[x] < depth[y])	swap(x,y);
	int d = depth[x] - depth[y];
	for(int i = 0; d; i++, d >>= 1)
		if(d & 1) 
			x = f[x][i];
	if(x == y) return x;
    for(int i = 20;i >= 0;i--)
		if(fa[x][i] != fa[y][i])
			x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}


